package com.majie.algorithm.sort;

import com.majie.common.SwapUtils;

/**
 * 三路快速排序
 * <p>
 * 之前上面的缺陷
 * 1.如果数组本来就是有序数组的话,会很耗时
 * 所以先打乱位置
 * 2.如果有大量的相等值
 *
 * @author majie
 * @date 2018-05-07
 */
public class QuickSort3 {

    public QuickSort3( ) {
    }

    /**
     * 排序
     * <p>
     * 1.找到零界点
     * 2.分别对零界点左右递归
     * 3.最后交换临界点和最左边
     */
    private static void sort(int[] arr, int left, int right) {


        //递归的边界条件
        if (left >= right) {
            return;
        }

        SwapUtils.swap(arr, left, (int) (Math.random() * (right - left + 1)) + left);

        int v = arr[left];
        int gt = right + 1;
        int lt = left;
        int i = left + 1;
        while (i < gt) {
            if (arr[i] > v) {
                SwapUtils.swap(arr, i, gt - 1);
                gt--;
            } else if (arr[i] < v) {
                SwapUtils.swap(arr, i, lt + 1);
                lt++;
                i++;
            } else {
                i++;
            }

        }
        //完成以后交换i和v
        SwapUtils.swap(arr, lt, left);
        sort(arr, left, lt - 1);
        sort(arr, gt, right);

    }


    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {10, 6, 8, 3, 6, 5, 9, 4, 3, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
